package com.haidechizi.sort;

import java.util.Arrays;

/**
 * @author: wangdejun
 * @create: 2020-04-14 10:03
 * 时间复杂度：O(logn)
 * 空间复杂度：O(logn)
 **/
public class QuickSort {

    public static void main(String[] args) {
        int[] array = new int[]{9, 3, 17, 8, 5, 6, 7, 3, 5, 6, 2, 1, 33};
        quickSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));

    }

    public static void quickSort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        int position = array[start];
        int low = start;
        int high = end;
        while (low < high) {
            while (low < high && array[high] >= position) {
                high--;
            }
            array[low] = array[high];
            while (low < high && array[low] < position) {
                low++;
            }
            array[high] = array[low];
        }
        array[low] = position;

        quickSort(array, start, low);
        quickSort(array, low + 1, high);
    }
}
